class Solution174 {
    public int calculateMinimumHP(int[][] dungeon) {
        int m = dungeon.length ;
        int n = dungeon[0].length ;
      
        // 状态表示: 从[i,j]为起点出发,到终点,所需要的最低健康点
          int[][] dp = new int[m+1][n+1] ;
        // 初始化 
       for(int i = 0 ; i <= m ; i ++) dp[i][n] = Integer.MAX_VALUE ;
       for(int j = 0 ; j <= n ; j ++) dp[m][j] = Integer.MAX_VALUE ; 
        dp[m-1][n] = 1 ; 
        dp[m][n-1] = 1 ;
       // 状态表示: 当前状态从 右边一个位置 和 下面一个位置得到
        for(int i=m-1 ; i >= 0 ; i --){
            for(int j=n-1 ; j >= 0 ; j --){      
                dp[i][j] = Math.min(dp[i+1][j] , dp[i][j+1]) -dungeon[i][j] ;
                if(dp[i][j] <= 0){
                    dp[i][j] = 1 ;
                }
            }
        }
       return dp[0][0] ;

    }
}